#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define EMPTY 0
#define NOT_EMPTY 1
typedef int Status;
typedef struct {
    char *ch;
    int length;
}String;

Status initString(String *S);
Status StrAssign(String *T,char *chars);
Status seeThroughTheString(String S);
int StrLength(String S);
int StrCmp(String S,String T);
Status ClearString(String *S);
Status Concat(String *S,String s1,String s2);
Status SubString(String S,String *sub,int position,int len);
int Index(String S,String T,int *position);
Status Replace(String *S,String T,String V);
Status StrInsert(String *S,int position,String T);
Status StrDelete(String *S,int position,int len);
int IndexWithOutOutPut(String S,String T,int *position);
void StrInsertWithOutOutPut(String *S,int position,String T);
void StrDeleteWithoutOutPut(String *S,int position,int len);
//KMP匹配算法部分
void getNext(String T,int *next);
int IndexKMP(String S,String T,int *position);

void opSystem(String *S) {
    int op = 0;
    int next[100];
    String T,V;
    String NewString;
    String sub;
//    T.ch = "ymjyyds";
//    T.length = 7;
//    V.ch = "xxpyyds";
//    V.length = 7;
    int position = 0,length = 0;
    printf("----------------------------------------------------------\n");
    printf("Please select what you want to do to the String:\n");
    printf("1: copy an existed String to another\n");
    printf("2 :see through the String if you have initialized one\n");
    printf("3 :get the length of the main String\n");
    printf("4 :compare two Strings,you shall enter the second string\n");
    printf("5 :concat two Strings,and return the result String\n");
    printf("6 :get the subString from position for a certain length\n");
    printf("7 :locate a String in the main String,if exist,return its position,else return ERROR\n");
    printf("8 :replace all the subString T with  new String V in the main String S\n");
    printf("9 :insert a String at a certain position in the main String\n");
    printf("10:delete a certain length at a certain position in the main String\n");
    printf("-1:clear the String\n");
    printf("0 :reinitialize the String\n");
    printf("20:input a String and get the next array\n");
    printf("21:use the KMP algorithm to test its advantage(the main String and SubString was given by the program)\n");
    printf("----------------------------------------------------------\n");
    scanf("%d",&op);
    switch (op) {
        case 1:
            StrAssign(&T,S->ch);
            opSystem(S);
            break;
        case 2:
            seeThroughTheString(*S);
            opSystem(S);
            break;
        case 3:
            StrLength(*S);
            opSystem(S);
            break;
        case 4:
            T.ch = "ABCABCABC";
            StrCmp(*S,T);
            opSystem(S);
            break;
        case 5:
            T.ch = "XYZXYZXYZ";
            Concat(&NewString,*S,T);
            opSystem(S);
            break;
        case 6:
            SubString(*S,&sub,position,length);
            opSystem(S);
            break;
        case 7:
            printf("Please input the subString:\n");
            char sub[100];
            scanf("%s",sub);
            T.ch = sub;
            T.length = strlen(sub);
            Index(*S,T,&position);
            opSystem(S);
            break;
        case 8:
            printf("Please enter the T string and V String:\n");
            char tString[100];
            char vString[100];
            scanf("%s",tString);
            scanf("%s",vString);
            T.ch = tString;
            T.length = strlen(tString);
            V.ch = vString;
            V.length = strlen(vString);
            Replace(S,T,V);
            opSystem(S);
            break;
        case 9:
            T.ch = "insert";
            T.length = 6;
            StrInsert(S,position,T);
            opSystem(S);
            break;
        case 10:
            StrDelete(S,position,length);
            opSystem(S);
            break;
        case -1:
            ClearString(S);
            printf("String has been cleared.\n");
            opSystem(S);
            break;
        case 0:
            initString(S);
            opSystem(S);
            break;
        case 20:
            getNext(*S,next);
            opSystem(S);
            break;
        case 21:
//            极端情况，测试用例，以说明KMP在一些情况下的优势，用朴素算法while循环执行95次，用KMp算法执行43次
            T.ch = "AAAAb";
            T.length = 5;
            V.ch = "AAAAAAAAAAAAAAAAAAAAAAb";
            V.length = 23;
            Index(V,T,&position);
            printf("----------\n");
            IndexKMP(V,T,&position);
            opSystem(S);
        default:
            break;
    }
}

int main() {
    setbuf(stdout,NULL);
    String S;
    S.ch = (char *) malloc(sizeof(char));
    initString(&S);
    opSystem(&S);
    return 0;
}
//初始化一个长度为length的串，随机赋值
Status initString(String *S) {
    char *p;
//    S->ch = (char *) malloc(sizeof(char));
    p = S->ch;
    printf("Please enter the length of this String\n");
    scanf("%d",&(S->length));
    srand(time(0));
    for (int i = 0; i < S->length; ++i) {
//        *p = rand() % 94 + 33;//ASCII码值33-126
        *p = rand() % 3 + 65;//大写字母ABC的组合
        p++;
    }
    *p = 0;
    seeThroughTheString(*S);
    return OK;
}
//将一个串copy到另一个
Status StrAssign(String *T,char *chars) {
//    T->ch = (char *) malloc(sizeof(char));
    T->length = 0;
    char *p = chars,*q = T->ch;
    while (*p) {
        *q = *p;
        q++;
        p++;
        T->length++;
    }
    *q = 0;
    printf("the new String is below:\n");
    seeThroughTheString(*T);
    return OK;
}
//遍历串，打印输出
Status seeThroughTheString(String S) {
    if (S.ch == NULL) return ERROR;
    printf("The String is below:\n");
    char *p;
    p = S.ch;
//    printf("[ ");
    while (*p != 0) {
        printf("%c ",*p);
        p++;
    }
    printf("\n");
    return OK;
}
//得到串长度
int StrLength(String S) {
    printf("the String length is %d\n",S.length);
    return S.length;
}
//比较串，若S>T,则返回大于0，反之返回小于0，S等于T则返回0
int StrCmp(String S,String T) {
    printf("String S is:");
    seeThroughTheString(S);
    printf("String T is:");
    seeThroughTheString(T);
    for (int i = 0; i < S.length && i < T.length; ++i) {
        if (S.ch[i] > T.ch[i]) {
            printf("String S > String T\n");
            return S.ch[i] - T.ch[i];
        } else if (S.ch[i] < T.ch[i]) {
            printf("String S < String T\n");
            return S.ch[i] - T.ch[i];
        }
    }
    printf("String S = String T\n");
    return 0;
}
//清空串，串中元素全部赋值为空
Status ClearString(String *S) {
    char *p = S->ch;
    while (*p != 0) {
        *p = 0;
        p++;
    }
    S->length = 0;
    return OK;
}
//拼接串，将s1和s2拼接到一起，并用S记录&返回
Status Concat(String *S,String s1,String s2) {
    S->ch = (char *) malloc(sizeof(char));
    char *p = s1.ch,*q = S->ch;
    S->length = 0;
    while (*p != 0) {
        *q = *p;
        q++;
        p++;
        S->length++;
    }
    p = s2.ch;
    while (*p != 0) {
        *q = *p;
        q++;
        p++;
        S->length++;
    }
    *q = 0;
    seeThroughTheString(*S);
    return OK;
}
//获取在一定位置，一定长度的子串
Status SubString(String S,String *sub,int position,int len) {
    printf("please enter the position and length:\n");
    scanf("%d %d",&position,&len);
    if (position + len > S.length + 1 || position <=0 || len <= 0) {
        printf("invalid input,func exits\n");
        return ERROR;
    }
    for (int i = position - 1,j = 0; i < position + len - 1; ++i,j++) {
        sub->ch[j] = S.ch[i];
        sub->ch[j + 1] = 0;
    }
    sub->length = len;
    seeThroughTheString(*sub);
    return OK;
}
//定位子串在主串中第一次出现的位置 本函数子串定位采用朴素匹配算法，在后续版本中再另写KMP匹配算法的函数
int Index(String S,String T,int *position) {
    //测试用例
//    S.ch = "ymjyydsxxpyyds";
//    S.length = 14;
//    T.ch = "dsx";
//    T.length = 3;
    int count = 0;
    char *i = S.ch,*j = T.ch;
    while (*i != 0 && *j != 0) {
        if (*i == *j) {
            ++i;
            ++j;
        } else {
            i -= (j - T.ch);
            i++;
            j = T.ch;
        }
        count++;
        if (*j == 0) {
            *position = i-S.ch-T.length+1;
            printf("the sub string is located at position %d\n",(i - S.ch) - T.length+1);
            printf("The Simple algorithm has use %d times to finish\n",count);
            return (i - S.ch - T.length);
        }
    }

}
//将主串中所有的子串1全部换成子串2,replace函数就是对定位，插入和删除的综合应用
Status Replace(String *S,String T,String V) {
//    S->ch = (char *) malloc(sizeof(char));
//    S->ch = "syymjyydsyys";
//    S->length = 12;
//    T.ch = "A";
//    T.length = 1;
//    V.ch = "a";
//    V.length = 1;
    int pos = 0;
    while(IndexWithOutOutPut(*S,T,&pos) != 0) {
        if (pos == 0) {
            printf("There is no String T in the main String\n");
            return ERROR;
        }
        StrDeleteWithoutOutPut(S,pos,T.length);
        StrInsertWithOutOutPut(S,pos,V);
    }
    seeThroughTheString(*S);
}
//在一定位置插入子串，形成新主串
Status StrInsert(String *S,int position,String T) {
    printf("Please enter the position you want to insert");
    scanf("%d",&position);
    if (position <= 0 || position > S -> length) {
        printf("Invalid input,func exits\n");
        return ERROR;
    }
    for (int i = S->length+T.length-1; i > position + T.length - 2; --i) {
        S->ch[S->length+T.length] = 0;
        S->ch[i] = S->ch[i - T.length];
    }
    for (int i = position - 1,j = 0; i < position + T.length - 1; ++i,++j) {
        S->ch[i] = T.ch[j];
        S->length++;
    }
    seeThroughTheString(*S);
    return OK;
}
//删掉在一定位置的的一定长度的子串
Status StrDelete(String *S,int position,int len) {
    printf("please enter the position and length:\n");
    scanf("%d %d",&position,&len);
    if (position + len > S->length + 1 || position <=0 || len <= 0) {
        printf("invalid input,func exits\n");
        return ERROR;
    }
    for (int i = position - 1; i < S->length - len; ++i) {
        S->ch[i] = S->ch[i + len];
        S->ch[i + len] = 0;
    }
    S->length -= len;
    seeThroughTheString(*S);
    return OK;
}
//和上文的定位插入删除操作一样，但是不带输出
int IndexWithOutOutPut(String S,String T,int *position) {
    *position = 0;
    char *i = S.ch,*j = T.ch;
    while (*i != 0 && *j != 0) {
        if (*i == *j) {
            ++i;
            ++j;
        } else {
            i -= (j - T.ch);
            i++;
            j = T.ch;
        }
        if (*j == 0) {
            *position = i-S.ch-T.length+1;
            return *position;
        }
    }
    return 0;
}
void StrInsertWithOutOutPut(String *S,int position,String T) {
    for (int i = S->length+T.length-1; i > position + T.length - 2; --i) {
        S->ch[S->length+T.length] = 0;
        S->ch[i] = S->ch[i - T.length];
    }
    for (int i = position - 1,j = 0; i < position + T.length - 1; ++i,++j) {
        S->ch[i] = T.ch[j];
        S->length++;
    }

}
void StrDeleteWithoutOutPut(String *S,int position,int len) {
    for (int i = position - 1; i < S->length - len; ++i) {
        S->ch[i] = S->ch[i + len];
        S->ch[i + len] = 0;
    }
    S->length -= len;
}

/*串的函数真的难写。。。。对字符串的操作要格外小心，不然很容易就segmentation fault了，
 * 我就是因为各种segmentation fault耗了一堆时间，哭了
 * 感觉这里的函数有的还是有bug，但是真的写不动了。。。。
 * 还要学KMP，先push了*/
//获取next数组
void getNext(String T,int *next) {
    int i = 1,j = 0;
    next[1] = 0;
    while (i < strlen(T.ch)) {
        if (j == 0 || T.ch[i-1] == T.ch[j-1]) {
            ++i;
            ++j;
            next[i] = j;
//            KMP算法的改进，采用nextval数组
//            if (T.ch[i-1]!=T.ch[j-1]) {
//               next[i]=j;
//            }
//            else{
//                next[i]=next[j];
//            }
        } else j = next[j];
    }
    printf("the next array is : ");
    for (int k = 1; k <= strlen(T.ch); ++k) {
        printf("%d",next[k]);
    }
    printf("\n");
}
//按照Kmp算法进行匹配
int IndexKMP(String S,String T,int *position) {
    int i = 0,j = 1;
    int next[100];
    getNext(T,next);
    int count = 0;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i - 1] == T.ch[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        count++;
    }
    if (j > T.length) {
        *position = i - T.length;
        printf("the subString is located at position %d\n",*position);
        printf("KMP has use %d times to finish\n",count);
        return i - T.length;
    }
    else return ERROR;
}